COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\magnification\magstephalf
C00010 ENDMK
C⊗;
\magnification\magstephalf
\input macro.tex
\def\today{\ifcase\month\or
  January\or February\or March\or April\or May\or June\or
  July\or August\or September\or October\or November\or December\fi
  \space\number\day, \number\year}
\baselineskip 14pt
\rm
\line{\sevenrm a56.tex[154,phy] \today\hfill}

\parskip 5pt
\bigskip
\line{\bf The Hennie-Stearns Theorem\hfill}

The Hennie-Stearns data structure stores the contents of a simulated stack
on a one-way-infinite tape in blocks, punctuated by block headers and end
markers. The blocks have three different densities (empty, half, and full)
designated by headers {\tt E}, {\tt H}, and~{\tt F}. 
The left and right end markers
are {\tt L} and~{\tt R}. If the stack content is {\tt abcdefg}, 
the tape content might~be
$${\tt LHa*FbcE****Hd*e*f*g*R}\,.$$
The length of each block but the first is the sum of all the lengths to its
left. The stack top is on the left, and no special stack bottom symbol is assumed.
An initially empty stack is represented by {\tt LE**R}. The home
position of the tape head is the left end.

Stack operations that do not cause over- or underflow of the first block are
easily simulated in constant time:

\smallskip
\disleft 20pt:$\bullet$:
Push({\tt a})  changes {\tt LE*} to {\tt LHa} and {\tt LHb*} to~{\tt LFab}.

\smallskip
\disleft 20pt:$\bullet$:
Pop changes {\tt LHa} to {\tt LE*} and {\tt LFab} to {\tt LHb*}, 
returning {\tt a} in either case.

\smallskip\noindent
A push on a tape that begins {\tt LF} requires that the information in contiguous
full blocks on the left end of the tape first be stretched to half density,
for example changing \hbox{\tt LFbcFdeHf*g*} to
\hbox{\tt LHb*Hc*Fdefg}.
This is done by copying the stack contents to a second tape, then copying
it back into the existing blocks at the correct densities and changing
the headers.

Similarly, a pop on a tape that begins {\tt LE} requires that information be
shrunk to the left, filling in contiguous empty left blocks to half density
information from the first nonempty block, for example changing
\hbox{\tt LE**E**E****Ha*b*c*d*}
to
\hbox{\tt LHa*Hb*Hc*d*E********}.

Exceptions arise when the stretch and shrink operations reach the right end
markers. If the shrink operation reaches~{\tt R}, an attempt to pop the empty
stack is happening, and an error halt suffices. If the stretch operation
reaches~{\tt R}, it should rewind both tapes, copy the contents of tape~2
at half density back into the preexisting blocks of tape~1, inserting
an overflow block at half density before the right end marker; for example,
\hbox{\tt LFabFcdR} becomes
\hbox{\tt LHa*Hb*He*d*R}.

A stretch or shrink operation on $i$~blocks takes $O(2↑i)$ steps. Because
it leaves the first $i-1$ blocks containing $2↑{i-1}$ characters at
half density, it need not be repeated until at least $2↑{i-1}$ pushes
and pops are simulated, so the total time spent on $i$-block stretching
or shrinking while simulating $t$~steps of stack operation is at most
$$O(2↑i)\left\lfloor{t\over 2↑{i-1}}\right\rfloor=O(t)\,.$$
Because these stretch and shrink operations only occur for $i≤\lg t$,
the total time spent simulating $t$~pushes and pops is 
$O(t)+O(\lg t)=O(t\lg t)$.

The value of the Hennie-Stearns structure is that one can simulate
{\sl several\/} stacks on different tracks
of a single one-way-infinite tape, and the home positions are all the
same, so no time is wasted moving between the home positions of the
several stacks. Therefore,

\proclaim Theorem. Any fixed number of initially empty stacks can be
simulated for $t$~steps in time $O(t\lg t)$, using two one-way-infinite
tapes.

\proclaim Corollary {\rm The Hennie-Stearns Theorem)}. Any fixed
number of tapes can be simulated for $t$~steps in time $O(t\lg t)$
using two one-way-infinite tapes. Anything any multitape Turing machine
can do in $t(n)$ steps can be done in $O\bigl(t(n)\lg t(n)\bigr)$
steps with two tapes.

The above construction is a free adaptation of the original Hennie-Stearns
construction, to simplify the proof.


\bigskip
\parindent0pt
\copyright 1986 Robert W. Floyd.
First draft (not published)
September 2, 1986.
%revised date;
%subsequently revised.

\bye